package hanjia;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2025/2/11-上午11:34
 * Since  :   1.0
 * Version:   1.0
 */
public class KMP {


    public int[] findNext(String s) {

        if (s.length() == 0) {
            return null;
        }
        int[] next = new int[s.length()];
        next[0] = 1;
        int j=0;
        for (int i = 1; i < next.length; i++) {
            while (j>0&&s.charAt(i)!=s.charAt(j)){
             j=next[i-1];

            }
            if (s.charAt(i)==s.charAt(j)){
                j++;
            }
            next[i]=j;


        }
        return next;
    }

    public int kmp(String source,String subString){

        int[] next = findNext(subString);
        int left=0;
        int right=0;
        while (left<source.length()){
            if (source.charAt(left)==subString.charAt(right)){
                left++;
                right++;
            }else {
                if (right>0){
                    right=next[right-1];
                }else {
                    left++;
                }


            }

            if (right==subString.length()){
                return left-right;
            }


        }



        return -1;


    }







    }



